Phase retrieval generally refers to the process of recovering a complete signal-of-interest from only intensity (i.e., magnitude) information relating to that signal. Phase retrieval applies to a number of important fields, including astronomy, computational biology, crystallography, digital communications, electron microscopy, neutron radiography, and optical imaging.
The purpose of phase retrieval is to recover a signal using the magnitude-square observations of its linear transformation. In fact, phase retrieval corresponds to a difficult nonconvex optimization problem where minimizing a multivariate quartic (i.e., fourth-order) polynomial is required. This problem is generally “NP-hard,” where NP-hardness (i.e., non-deterministic polynomial-time hardness), in computational complexity theory, is a class of problems that are, informally, “at least as hard as the hardest problems in NP.” More precisely, a problem, H, is NP-hard when every problem, L, in NP can be reduced in polynomial time to H. That is, a given solution for problem L can be verified to be a solution for problem H in polynomial time. As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard.
Traditional phase retrieval techniques involve restoring a time-domain signal from its power spectrum observations, although the Fourier transform can be generalized to any linear mappings. Conventional approaches include the Gerchherg-Saxton (GS) technique, the Wirtinger Flow (WF) technique, the PhaseLift technique, and the PhaseCut technique. The GS and WF techniques directly deal with the nonconvex problem formulation by adopting alternating minimization and gradient descent, respectively. On the other hand, the PhaseLift technique and the PhaseCut technique relax the nonconvex problem to a convex program. However, these approaches have the drawbacks of requiring lengthy observations, a relatively large number of iterations, and/or high computational complexity.